#include "headfiles.h"


// If found, return value is true, and the output is in the index_i,
// and index_j;
// If not found, return value is false
bool searchSortedMatrix1(int *matrix, 
                         int m, 
                         int n, 
                         int elem, 
                         int &index_i, 
                         int &index_j) {
    // Start from the top right corner
    int i = 0;
    int j = n - 1;
    int loc;
    while (j >= 0 && i < m) {
        int loc = i * n + j;
        if (matrix[loc] == elem) {
            index_i = loc / n;
            index_j = loc % n;

            return true;
        }
        else if (matrix[loc] > elem) {
            --j;
        }
        else {
            ++i;
        }
    }

    index_i = -1;
    index_j = -1;

    return false;
}

bool searchSortedMatrix2(int *matrix, 
                         int m, 
                         int n, 
                         int elem, 
                         int &index_i, 
                         int &index_j) {
    // Start from the bottom left corner
    int i = m - 1;
    int j = 0;
    int loc;
    while (j < n && i >= 0) {
        int loc = i * n + j;
        if (matrix[loc] == elem) {
            index_i = loc / n;
            index_j = loc % n;

            return true;
        }
        else if (matrix[loc] > elem) {
            --i;
        }
        else {
            ++j;
        }
    }

    index_i = -1;
    index_j = -1;

    return false;
}

